package org.xingole.leetcode.dp;

import java.util.Arrays;

public class NonOverlappingIntervals {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 1. Sorting the given interval list based on the end points.
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        return selectIntervals3(intervals);
    }

    /**
     * Adapted from CLRS
     * 
     */
    private int selectIntervals(int[][] intervals) {
        int n = intervals.length;
        /*
         * 1. Create two fictitious activities - start a[0] and end a[n].
         */
        int[][] activities = new int[n + 2][2];
        activities[0][1] = Integer.MIN_VALUE;
        activities[n + 1][0] = Integer.MAX_VALUE;
        System.arraycopy(intervals,  0,
                         activities, 1,
                         n);  // O(n)
        /*
        * 2. Let us denote by S_ij the set of activities that start after 
        * activities a_i finishes and that finish before activity a_j starts.
        * If we denote the size of an optimal solution for the set S_ij by
        * dp[i][j], then we would have the recurrence:
        *                      0                        if S_ij = empty,          
        *        dp[i][j]   max(dp[i][k] + dp[k][j] + 1) if S_ij != empty.
        * for all a_k in S_ij.
        */
        int[][] dp = new int[n + 2][n + 2];
        // base case:
        for(int i = 0; i < n + 1; i++) {
            dp[i][i] = 0;
            dp[i][i + 1] = 0;
        }
        dp[n + 1][n + 1] = 0;
        
        for(int len = 2; len < n + 2; len++) {
            for(int i = 0; i < n - len + 2; i++) {
                int j = i + len;
                dp[i][j] = 0;
                for(int k = j - 1; activities[i][1] < activities[k][1]; k--) {
                    if(activities[i][1] <= activities[k][0] && 
                      activities[k][1] <= activities[j][0] && 
                      dp[i][k] + dp[k][j] + 1 > dp[i][j]) 
                    {
                        // update the value
                        dp[i][j] = dp[i][k] + dp[k][j] + 1;
                    }
                }
            }
        } // O(n^3)
        int ans = dp[0][n+1];
        return n - ans;
    }

    /**
     * Using DP based on starting point
     * 
     *   Let dp[i] stores the maximum number of valid intervals that can be
     * included in the final list if the intervals upto the ith interval 
     * only are considered, including itself.  
     *   While finding dp[i+1], we can't consider the value of dp[i] only, 
     * because it could be possible that the ith or any previous interval
     * could be overlapping with (i + 1)th interval. 
     *   Thus, we need to consider the maximum of all dp[j]'s such that 
     * j <= i and jth interval and ith don't overlap, to evaluate dp[i+1].
     *   Therefore, the equation for dp[i+1] becomes:
     *        dp[i+1] = max(dp[j]) + 1,
     *   such that jth interval and ith don't overlap, for all j <= i.
     *   In the end, to obtain the maximum number of intervals that can
     * be included in the final list we need to find the maximum value in
     * the dp array. The final result will be total number of intervals 
     * given less the result just obtained(intervals.length - ans).
     * 
     * Time Complexity
     *    T(n) = O(n^2)
     */
    private int selectIntervals1(int[][] intervals) {
        int[] dp = new int[intervals.length];
        
        // base case
        dp[0] = 1;

        // down-up method
        int ans = 1;
        for(int i = 1; i < dp.length; i++) {
            int max = 0;
            for(int j = i - 1; j >= 0; j--) {
                if((intervals[j][1] <= intervals[i][0])) {
                    max = Math.max(dp[j], max);
                }
            }
            dp[i] = max + 1;
            ans = Math.max(ans, dp[i]);
        }

        return intervals.length - ans;
    }

    /**
     * Using DP based on the end points
     * 
     *   Let dp[i] store the maximum number of intervals that can 
     * be included in the final list if the intervals only upto the 
     * ith index in the sorted list are considered. 
     *   Thus, in order to find dp[i+1] now, we've to consider two cases:
     * Case 1:
     *   The interval corresponding to (i+1)th interval needs to be included
     * in the final list to obtain the minimum number of removals.
     *
     * Case 2:
     *   The interval corresponding to (i+1)th interval needs to be removed from
     * the final list to obtain the minimum number of removals.
     *
     * Timep Complexity
     *   T(n) = O(n^2)
     */
    private int selectIntervals2(int[][] intervals) {
        int[] dp = new int[intervals.length];
        
        // base case
        dp[0] = 1;

        // down-up method
        int ans = 1;
        for(int i = 1; i < dp.length; i++) {
            int max = 0;
            for(int j = i - 1; j >= 0; j--) {
                if((intervals[j][1] <= intervals[i][0])) {
                    max = Math.max(dp[j], max);
                    break;
                }
            }
            dp[i] = Math.max(max + 1, dp[i - 1]);
            ans = Math.max(ans, dp[i]);
        }

        return intervals.length - ans;
    }

    /**
     * Using Greedy Approach based on end points (Adapted from CLRS)
     *  
     *  Time complexity
     *     T(n) = O(n + nlgn) = O(nlgn)
     */
    private int selectIntervals3(int[][] intervals) {
        // the end points for compatible activities from 0 to i - 1
        int end = intervals[0][1];

        int ans = 1; 
        for(int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] >= end) {
                end = intervals[i][1];
                ans++;
            }
        }

        return intervals.length - ans;
    }
}
